Packets from different flows are received at a network device which represents a queuing point where packets belonging to various flows may become backlogged while waiting to be transmitted from the network device. A scheduler processes information associated with the head packet in each queue to determine which packet should be transmitted. The scheduler guarantees a minimum packet transmission rate to each queue where the sum of the guaranteed transmission rates must not be greater than the packet transmission rate of the channel. Thus, the packet transmission rate of the channel is much greater than the packet transmission rate guaranteed to any queue.
Packets are transmitted serially through the channel. When the channel is idle the scheduler selects a head packet from one of the queues, based on some priority scheme, and forwards it to the channel for transmission. Each queue has its packets transmitted as if it were the only source using a channel having a channel packet transmission rate equal to the guaranteed packet transmission rate of the queue.
Network devices are required to support many thousands of multicast groups. To provide a queue per multicast group can be too costly as queue scheduling is difficult to scale especially at high bandwidth. Practical designs let multiple groups share a queue in order to reduce the number of queues, but this creates head of line blocking (HOLB).
At the transmitter, head of line blocking occurs because queues are implemented as first-in-first-out transmit buffers. If the packet at the head of the buffer experiences backpressure then it blocks the transmission of all following packets in the buffer.